/*
 * @Author: lei
 * @Description:
 * 从输入遍历序列中还原二叉树(假设输入的遍历数组的结果中都不含重复的数)
 * @FilePath: /树/create_tree.cc
 */
#include <string>
#include <vector>

#include "definition.h"

// 通过中序序列和前序序列还原二叉树
TreeNode* CreateTreeFromPreIn(vector<int>& inorder, vector<int>& preorder,
                              int inorder_left, int inorder_right,
                              int preorder_left, int preorder_right) {
  if (preorder_left > preorder_right) return nullptr;
  TreeNode* new_node = new TreeNode(preorder[preorder_left]);
  int root_index;
  for (root_index = inorder_left; root_index <= inorder_right; root_index++) {
    if (inorder[root_index] == preorder[preorder_left]) break;
  }
  int left_subtree_node_count = root_index - inorder_left;
  new_node->left = CreateTreeFromPreIn(inorder, preorder, inorder_left,
                                       root_index - 1, preorder_left + 1,
                                       preorder_left + left_subtree_node_count);
  new_node->right = CreateTreeFromPreIn(
      inorder, preorder, root_index + 1, inorder_right,
      preorder_left + left_subtree_node_count + 1, preorder_right);
  return new_node;
}

// 通过中序序列和后序序列还原二叉树
TreeNode* CreateTreeFromInPost(vector<int>& inorder, vector<int>& postorder,
                               int inorder_left, int inorder_right,
                               int postorder_left, int postorder_right) {
  if (postorder_left > postorder_right) return nullptr;
  TreeNode* root = new TreeNode(postorder[postorder_right]);
  int root_index;
  for (root_index = inorder_left; root_index <= inorder_right; root_index++) {
    if (inorder[root_index] == postorder[postorder_right]) break;
  }
  int left_subtree_node_count = root_index - inorder_left;
  root->left = CreateTreeFromInPost(
      inorder, postorder, inorder_left, root_index - 1, postorder_left,
      postorder_left + left_subtree_node_count - 1);
  root->right = CreateTreeFromInPost(
      inorder, postorder, root_index + 1, inorder_right,
      postorder_left + left_subtree_node_count, postorder_right - 1);
  return root;
}

// 通过层次遍历和中序遍历还原二叉树
// 由层次遍历和中序遍历序列生成二叉树的办法（自己的办法）：二叉树的根节点在层次遍历序列中要先于
// 其子树首先被访问，所以层次遍历序列中第一个与中序序列中匹配的字符为中序序列的根结点
TreeNode* CreateTreeFromInLevel(vector<int>& inorder, vector<int>& levelorder,
                                int inorder_left, int inorder_right,
                                int levelorder_left, int levelorder_right) {
  if (levelorder_left > levelorder_right) return nullptr;
  TreeNode* node = new TreeNode;
  int i, j;
  int flag = 0;
  // 寻找根结点，若level中第一个与in中元素匹配的即为根结点
  for (i = levelorder_left; i < levelorder_right; i++) {
    for (j = inorder_left; j < inorder_right; j++) {
      if (levelorder[i] == inorder[j]) {
        flag = 1;
        break;
      }
    }
    if (flag == 1) break;
  }
  node->val = levelorder[i];
  node->left = CreateTreeFromInLevel(inorder, levelorder, inorder_left, j - 1,
                                     levelorder_left + 1, levelorder_right);
  node->right = CreateTreeFromInLevel(inorder, levelorder, j + 1, inorder_right,
                                      levelorder_left + 1, levelorder_right);
  return node;
}

// 通过遍历数组建立树
TreeNode* CreateTreeFromVector(vector<string> nodes) {
  int len = nodes.size();
  int current = 0;
  vector<TreeNode*> pNodes;
  TreeNode* pCurNode;
  for (; current < len; ++current) {
    if (nodes[current] != "#")
      pCurNode = new TreeNode(stoi(nodes[current]));
    else
      pCurNode = nullptr;
    // 如果该节点有父节点，设置一下其父节点的指针指向
    if (current > 0) {
      int parentIdx = (current - 1) >> 1;
      if (!pNodes[parentIdx]) continue;
      if (current % 2 != 0)  // 是左孩子
        pNodes[parentIdx]->left = pCurNode;
      else  // 是右孩子
        pNodes[parentIdx]->right = pCurNode;
    }
    pNodes.push_back(pCurNode);
  }
  return pNodes[0];
}
